The present invention is related to the field of link-state network routing protocols such as the Open Shortest Path First (OSPF) routing protocol.
In the operation of link-state routing protocols, network routers maintain independent copies of a link-state database and use the stored link-state information to conduct message routing operations. The routers communicate link-state advertisements among themselves to make sure that all routers are apprised of changes to links in the network, so that routing decisions are generally made on up-to-date information concerning the current network topology and the performance characteristics of the various network links. A link-state advertisement generated by a given router is generally broadcast, or “flooded”, to all the other routers in an area, and each router uses the information in each advertisement to make corresponding changes in its link-state database.
Currently, OSPF routers generate link-state advertisements in two ways. First, there is a periodic broadcast of all the entries in a router's link-state database. This operation can be useful to initialize other routers and to replace outdated entries in the databases of other routers. Additionally, routers originate link-state advertisements in a change-driven manner. That is, a router for a given link monitors certain operating parameters of the link and generates a link-state advertisement when any of the parameters changes. For example, it is common for routers to monitor changes in the unreserved bandwidth of a link. This monitoring can be used in conjunction with thresholds to give a measure of control over how often link-state advertisements are generated. For example, a router can monitor for a change of a specified amount, such as 10%, in unreserved bandwidth since the last link-state advertisement was generated for the link, and generate a new link-state advertisement only when that condition is satisfied.
The flooding of link-state advertisements can result in operating inefficiency in the network. On the one hand, it is important that changes be propagated throughout the network promptly, so that good routing decisions can be made. However, the transmission and processing of link-state advertisements consumes network resources that might be better spent processing data messages. As the volume of link-state advertisements grows, the efficiency of network operation diminishes. While techniques such as the use of thresholds can be used to reduce link-state advertisement traffic to some extent, there is still substantial room for improvement in the operating efficiency of link-state routing protocols.